package com.yangli.leecode.mashib.interview;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/10 14:26
 */
public class FortySeven {
    public static void main(String[] args){
        System.out.println(FortySeven.countPrimes(100));
        System.out.println(FortySeven.countPrimes2(499979));

    }


    //2埃氏筛
    public static int countPrimes(int n){
        if (n < 2) {
            return 0;
        }
        int[] primes = new int[n + 1];
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (primes[i] == 0) {
                ans++;
                for (int j = i * i; j < n; j += i) {//筛选从自身开始那些数不为素数，之前的数如果是素数已经执行过了，如果不是也没必要计算，肯定计算过了
                    primes[j] = 1;
                }
            }
        }
        return ans;
    }

    //3 线性筛选 降低重复计算，不能完全消除
    public static int countPrimes2(int n){
        if (n < 3) {
            return 0;
        }
        int[] primes = new int[n + 1];
        int count = n / 2;//偶数肯定是不为素数了
        for (int i = 3; i < n; i += 2) {
            if (primes[i] == 0) {
                if ((long) i * i < n) {
                    for (int j = i * i; j < n; j += 2 * i) {
                        if (primes[j] == 0) {//有可能还会又部分重复
                            primes[j] = 1;//不为素数
                            count--;
                        }
                    }
                }
            }
        }
        return count;
    }

}
